class Solution:
    """
    132. 分割回文串 II
    https://leetcode-cn.com/problems/palindrome-partitioning-ii/
    @date: 2021年1月2日17:06:38
    @author: mizzle rain
    """

    def minCut(self, s: str) -> int:
        m = len(s)
        if m == 1:
            return 0
        c = [[False for _ in range(m)] for _ in range(m)]
        for i in range(m-1, -1, -1):
            for j in range(i, m):
                c[i][j] = s[i] == s[j] and (i + 1 > j - 1 or c[i+1][j-1])
        # dp[i] 表示：以 s[0...i] 中的回文串的最小个数
        dp = [1010 for _ in range(m+1)]
        dp[0] = 0
        for i in range(1, m+1):
            for j in range(1, i+1):
                if c[j-1][i-1]:
                    dp[i] = min(dp[i], dp[j-1] + 1)
            print(dp)
        return dp[-1]-1

        """
        [0, 1, 1010, 1010]
        [0, 1, 1, 1010]
        [0, 1, 1, 2]
        i = 1
            j = 1 
                dp[1] = min(1010, 0 + 1)
        i = 2
            j = 1
                dp[2] = min(1010, 0 + 1)
            j = 2
                dp[2] = min(1, 1 + 1)
        i = 3    
            j = 1
                dp[3] = 1010
            j = 2
                d[3] = 1010
            j = 3
                dp[3] = min(1010, 1 + 1)
        """


if __name__ == "__main__":
    s = Solution()
    ans = s.minCut("aab")
    print(ans)
